#ifndef TERNARY_TREE_H
#define TERNARY_TREE_H
#include <vector>

template<class T, class U> struct TNode
{
	T									splitKey;
	TNode<T, U>*				lowKeyID;
	TNode<T, U>*				eqKeyID;
	TNode<T, U>*				highKeyID;
	U*									userData;
	TNode()
		: splitKey()
		, lowKeyID(0)
		, eqKeyID(0)
		, highKeyID(0)
		, userData(0)
	{
	}
};

// d store the address of userData
template<class T, class U>
TNode<T, U>* insert(TNode<T, U>* p, T* s, U**& d)
{
	if (!p)
	{
		p = new (TNode<T, U>);
		p->splitKey = *s;
		if (*s == 0)
		{
			d = &(p->userData);
		}
	}
	if (*s < p->splitKey)
	{
		p->lowKeyID = insert(p->lowKeyID, s, d);
	}
	else if (*s == p->splitKey)
	{
		if (*s != 0)
		{
			p->eqKeyID = insert(p->eqKeyID, ++s, d);
		}
		else
		{
			d = &(p->userData);
		}
	}
	else 
	{
		p->highKeyID = insert(p->highKeyID, s, d);
	}
	return p;
}

// if insert an identical key, this function won't insert any new node
template<class T, class U>
TNode<T, U>* insert(TNode<T, U>* p, T* s, U* d = 0)
{
	if (!p)
	{
		p = new (TNode<T, U>);
		p->splitKey = *s;
		p->lowKeyID = p->eqKeyID = p->highKeyID = 0;
		p->userData = 0;
		if (*s == 0)
			p->userData = d;
	}
	if (*s < p->splitKey)
	{
		p->lowKeyID = insert(p->lowKeyID, s, d);
	}
	else if (*s == p->splitKey)
	{
		if (*s != 0)
		{
			p->eqKeyID = insert(p->eqKeyID, ++s, d);
		}
	}
	else 
	{
		p->highKeyID = insert(p->highKeyID, s, d);
	}
	return p;
}

// get the leave node
template<class T, class U>
TNode<T, U>* search(TNode<T, U>* head, T* s)
{
	TNode<T, U>* p;
	p = head;
	while (p)
	{
		if (*s < p->splitKey)
		{
			p = p->lowKeyID;
		}
		else if (*s == p->splitKey)
		{
			if (*s++ == 0)
				return p;
			p = p->eqKeyID;
		}
		else
		{
			p = p->highKeyID;
		}
	}
	return 0;
}

template<class T, class U>
void deleteKey(TNode<T, U>* root, T* s)
{
	TNode<T, U>* parent = searchParent(root, s);
	
}

template<class T, class U>
void destroyFrom(TNode<T, U>* parent, TNode<T, U>* p)
{
	std::vector<TNode<T, U>* > nodes;
	bool isLeaf = true;
	nodes.push_back(p);
	TNode<T, U>* curParent = parent;
	while (p)
	{
		isLeaf = (!p->eqKeyID) && (!p->lowKeyID) && (!p->highKeyID);
		if (isLeaf)
		{
			if (curParent && curParent->lowKeyID == p)
			{
				curParent->lowKeyID = 0;
			}
			else if (curParent && curParent->eqKeyID == p)
			{
				curParent->eqKeyID = 0;
			}
			else if (curParent && curParent->highKeyID == p)
			{
				curParent->highKeyID = 0;
			}
			std::cout << p->splitKey << "\n";
			delete p;
			nodes.pop_back();
			size_t nodeSize = nodes.size();
			if (nodeSize >= 1)
			{
				p = nodes.back();
			}
			else
			{
				p = 0;
			}
			if (nodeSize >= 2)
			{
				curParent = nodes[nodeSize - 2];
			}
			else
			{
				curParent = parent;
			}
			continue;
		}
		if (p->lowKeyID)
		{
			curParent = p;
			p = p->lowKeyID;
			nodes.push_back(p);
			continue;
		}
		if (p->eqKeyID)
		{
			curParent = p;
			p = p->eqKeyID;
			nodes.push_back(p);
			continue;
		}
		if (p->highKeyID)
		{
			curParent = p;
			p = p->highKeyID;
			nodes.push_back(p);
			continue;
		}
	}
}

template<class T, class U>
TNode<T, U>* searchParent(TNode<T, U>* root, T* s)
{
	TNode<T, U>* parent = 0;
	TNode<T, U>* head = root;
	while (head)
	{
		if (*s == head->splitKey)
		{
			if (*s++ == 0)
				return parent;
			head = head->eqKeyID;
		}
		else if (*s < head->splitKey)
		{
			parent = head;
			head = head->lowKeyID;
		}
		else if (*s > head->splitKey)
		{
			parent = head;
			head = head->highKeyID;
		}
	}
	return parent;
}

template<class T, class U>
TNode<T, U>* searchHead(TNode<T, U>* root, T* s)
{
	TNode<T, U>* p;
	TNode<T, U>* head = 0;
	p = root;
	while (p)
	{
		if (*s < p->splitKey)
		{
			p = p->lowKeyID;
			head = 0;
		}
		else if (*s == p->splitKey)
		{
			if (!head)
				head = p;
			if (*s++ == 0)
				return head;
			p = p->eqKeyID;
		}
		else
		{
			p = p->highKeyID;
			head = 0;
		}
	}
	return head;
}


template<class T, class U>
TNode<T, U>* queryLeafNode(TNode<T, U>* p)
{
	if (!p)
		return 0;
	TNode<T, U>* next = p;
	while(next->eqKeyID)
	{
		next = next->eqKeyID;
	}
	if (next->splitKey == 0)
		return next;
	return 0;
}

template<class T, class U>
void pmsearch(TNode<T, U>* p, T* s, std::vector<TNode<T, U>* >& result);

const int MAX_SEARCH = 100000;
void pmsearch(TNode<char, int>* p, char* s, std::vector<TNode<char, int>* >& result)
{
	static char* record[MAX_SEARCH];
	static int top;
	if (!p)
		return;
	if (*s == '.' || *s < p->splitKey)
		pmsearch(p->lowKeyID, s, result);
	if (*s == '.' || *s == p->splitKey)
		if (p->splitKey && *s)
			pmsearch(p->eqKeyID, s+1, result);
	if (*s == 0 && p->splitKey == 0)
	{
		record[top++] = (char*)p->eqKeyID;
		result.push_back(p);
	}
	if (*s == '.' || *s > p->splitKey)
		pmsearch(p->highKeyID, s, result);
}

template<class T, class U>
void nearSearch(TNode<T, U>* p, T* s, int d);

template<class U>
void nearSearch(TNode<char, U>*, char* s, int d)
{
	
}

template<class T, class U>
void dfs(TNode<T, U>* p)
{
	if (!p)
		return;
	std::cout << p->splitKey << " \n";
	if (p->userData)
	{
		std::cout << *(p->userData) << "\n";
	}
	if (p->lowKeyID)
	{
		dfs(p->lowKeyID);
	}
	if (p->eqKeyID)
	{
		dfs(p->eqKeyID);
	}
	if (p->highKeyID)
	{
		dfs(p->highKeyID);
	}
}

//template<class T, class U>
//void
#endif